Computing systems generally must include techniques for allocating limited resources to programs, processes, operating system kernels, or threads. Limited resources may include, but are not limited to, blocks of memory, disk blocks, blocks of mass storage, I/O bandwidth, CPU cycles, system data structures, and the like. Operating system kernels typically include data structures and methods for allocating and freeing limited resources. However, these techniques are not necessarily limited to operating system kernels, or even to operating systems.
A CPU cache is a block of memory that is used to temporarily store and access data that is likely to be used again. A CPU cache is a block of fast memory that is used by a CPU to access data. Typically, access to data in a CPU cache is faster than access to data in a computer's main memory or other data storage. A CPU cache is made up of a number of cache lines, each cache line being a unit of cache that is read from or written to by the CPU.
Generally, it is desirable to employ efficient techniques for allocating limited resources. Efficient in this context may mean an improvement in time, processing time, amount of memory, or other resources. Therefore, it is with respect to these considerations and others that the present invention has been made.